package NO05;

/*
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 */
public class reConstructBinaryTree {
	static class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;

	    TreeNode(int x) {
	        val = x;
	    }
	}
	
	public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
		TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
		return root;
	}
	
	private static TreeNode reConstructBinaryTree(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){
		if(startPre > startIn || endPre > endIn){
			return null;
		}
		TreeNode root = new TreeNode(pre[startPre]);
		
		for(int i=startIn;i<endIn;i++){
			if(in[i] == pre[startPre]){
				root.left = reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
				root.right = reConstructBinaryTree(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
				break;
			}
		}
		
		return root;
	}
	
	public static void main(String[] args) {
		int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
		int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
		TreeNode root = reConstructBinaryTree(pre,in);
		System.out.println(root.val);
		System.out.println(root.left.val);
	}
	
	
	
}
